package com.shuang.dp24;

class Solution {
    //动态规划
    public int maxProfit(int[] prices) {

        if (prices == null || prices.length == 0)
            return 0;

        int length = prices.length;

        // dp[i][0]代表第i天持有股票的最大收益
        // dp[i][1]代表第i天不持有股票的最大收益
        int[][] dp = new int[length][2];

        int result = 0;

        //初始化
        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        for (int i = 1; i < length; i++) {

            //当天持有股票 可以由前一天持有 和 当天买入持有股票得来
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);

            //当天不持有股票由 当天卖掉股票 即前一天持有股票收益加上当天卖掉的收益 
            //和前一天就不持有股票得来          
            dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
        }

        return dp[length - 1][1];
    }
}